//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 
//
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 
//
// 
//
// 示例 1: 
//
// 
//输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5
// 
//
// 示例 2: 
//
// 
//输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
//输出: 4 
//
// 
//
// 提示： 
//
// 
// 1 <= k <= nums.length <= 104 
// -104 <= nums[i] <= 104 
// 
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 
// 👍 1485 👎 0

import java.util.PriorityQueue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution215 {
    /**
     * 解题思路：
     * 利用优先级队列 的大顶堆特性， 取第k个最大值
     *
     * 解答成功:
     * 			执行耗时:5 ms,击败了46.65% 的Java用户
     * 			内存消耗:41.6 MB,击败了6.43% 的Java用户
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest1(int[] nums, int k) {

        PriorityQueue<Integer> queue = new PriorityQueue<>(nums.length, (o1, o2) -> o2 - o1);
        for (int num : nums) {
            queue.add(num);
        }
        for(int i=0; i<k-1; i++) {
            queue.poll();
        }
        return queue.peek();
    }

    /**
     * 解题思路：
     * 1.先对原数组做快速排序
     * 2.找出第k个最大数据
     *
     * 解答成功:
     * 			执行耗时:34 ms,击败了10.36% 的Java用户
     * 			内存消耗:41.3 MB,击败了14.68% 的Java用户
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest2(int[] nums, int k) {

        int left = 0, right = nums.length-1;
        quickSort(nums, left, right);
        return nums[nums.length-k];
    }

    private void quickSort(int[] nums, int left, int right) {
        int l = left, r = right, pivot = nums[left];
        while(l < r) {
            while(nums[l] < pivot) {
                l++;
            }

            while(nums[r] > pivot) {
                r--;
            }

            if(l >= r) break;

            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;

            if(nums[l] == pivot) {
                r--;
            }
            if(nums[r] == pivot) {
                l++;
            }
        }

        if(l == r) {
            l++;
            r--;
        }

        if(r > left) {
            quickSort(nums, left, r);
        }

        if(l < right) {
            quickSort(nums, l, right);
        }
    }

    /**
     * 解题思路：
     * 数组的插入排序，从大到小
     * 当插入第i == k-1个元素时返回
     * 解答成功:
     * 			执行耗时:34 ms,击败了10.36% 的Java用户
     * 			内存消耗:41.6 MB,击败了6.93% 的Java用户
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {

        for (int i = 0; i < nums.length; i++) {
            int tmpMax = nums[i];
            for (int j = i+1; j < nums.length; j++) {
                if(nums[j] > tmpMax) {
                    nums[i] = nums[j];
                    nums[j] = tmpMax;
                    tmpMax = nums[i];
                }
            }
            if(i==(k-1)) {
                return tmpMax;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        new Solution215().findKthLargest(new int[]{3,2,1,5,6,4}, 2);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
